翻訳と辞書 Words near each other ・ Acy, Louisiana ・ Acy-en-Multien ・ Acy-Romance ・ ACY1 ・ Acyanotic heart defect ・ Acyclania ・ Acyclania schadei ・ Acyclania tenebrosa ・ Acyclic ・ Acyclic coloring ・ Acyclic dependencies principle ・ Acyclic diene metathesis ・ Acyclic graph ・ Acyclic model ・ Acyclic object ・ Acyclic orientation ・ Acyclic space ・ Acygnatha ・ Acygonia ・ Acyl ・ Acyl azide ・ Acyl carrier protein ・ Acyl carrier protein synthase ・ Acyl chloride ・ Acyl CoA dehydrogenase ・ Acyl halide ・ Acyl-(acyl-carrier-protein) desaturase ・ Acyl-(acyl-carrier-protein)—phospholipid O-acyltransferase ・ Acyl-(acyl-carrier-protein)—UDP-N-acetylglucosamine O-acyltransferase ・ Acyl-CoA Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Acyclic orientation ： ウィキペディア英語版 Acyclic orientation In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint. The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has ''k'' vertices if and only if it can be colored with ''k'' colors.〔.〕 For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if $G$ is a planar graph, and orientations of $G$ are transferred to orientations of the planar dual graph of $G$ by turning each edge 90 degrees clockwise, then a totally cyclic orientation of $G$ corresponds in this way to an acyclic orientation of the dual graph and vice versa.〔.〕 This duality extends to nonplanar graphs as well, via the Tutte polynomial $T\_G$ of a graph $G$, which can be used to count both types of orientations: the number of acyclic orientations of $G$ is $T\_G(2,0)$ and the number of totally cyclic orientations is $T\_G(0,2)$.〔.〕 The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial $\backslash chi\_G$: there are $|\backslash chi\_G(-1)|$ different acyclic orientations.〔.〕 The set of all acyclic orientations of a given graph may be given the structure of a partial cube, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge.〔.〕 An acyclic orientation of a complete graph is called a transitive tournament, and is equivalent to a total ordering of the graph's vertices. In such an orientation there is in particular exactly one source and exactly one sink; more generally, an acyclic orientation with a unique source and a unique sink is called a bipolar orientation.〔.〕 ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Acyclic orientation」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.